package com.bee.剑指offer;

/**
 * 输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。
 * （注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
 */
public class 两个链表的第一个公共结点 {


    /**
     * 两给指针，以相同的速度，一个个节点遍历，最终必定走到一起，
     * 1，有相同的节点(公共节点，相遇)
     * 2，没有公共的节点，N1，N2指针都将两张链表遍历完，都指为null
     */
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode n1 = pHead1;
        ListNode n2 = pHead2;
        while (n1 != n2) {
//            if(n1 == null) {
//                // n1为null遍历链表二
//                n1 = pHead2;
//            } else {
//                n1 = n1.next;
//            }
//            if(n2 == null) {
//                n2 = pHead1;
//            } else {
//                n2 = n2.next;
//            }
            n1 = (n1 == null) ? pHead2 : n1.next;
            n2 = (n2 == null) ? pHead1 : n2.next;
        }
        return n1;
    }

    public ListNode findFirst(ListNode pHead1, ListNode pHead2) {
        ListNode n1 = pHead1;
        ListNode n2 = pHead2;
        while (n1 != n2) {
            n1 = n1 == null ? pHead2 : n1.next;
            n2 = n2 == null ? pHead1 : n2.next;
        }
        return n1;
    }

    public static void main(String[] args) {

    }
}
